#include<bits/stdc++.h>
using namespace std;
inline int read()
{
	int x=0;char ch=getchar();
	while(!isdigit(ch)) ch=getchar();
	while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x;
}
typedef long long ll;
const int N=1e6+10;
int k,T1=1,T2,ans,a[N],b[N],numl[N],numr[N];
bool check()
{
	for(int i=numl[T2]+1;i<numr[T2];i++) if(a[i]) return 1;
	int Mx=k-1,Mn=0;
	if(!a[numl[T2]]) goto L;
	for(int i=0;i<k;i++) b[i]=a[i];
	--b[numl[T2]];
	while(~Mx&&!b[Mx]) Mx--;
	for(int i=T2-1;i;i--)
	{
		if(Mx>numl[i]) return 1;
		if(Mx<numl[i]) goto L;
		--b[Mx];
		while(~Mx&&!b[Mx]) Mx--;
	}
	return 1;
L:	if(!a[numr[T2]]) return 0;
	for(int i=0;i<k;i++) b[i]=a[i];
	--b[numr[T2]];
	while(Mn<k&&!b[Mn]) Mn++;
	for(int i=T2-1;i;i--)
	{
		if(Mn>numr[i]) return 0;
		if(Mn<numr[i]) return 1;
		--b[Mn];
		while(~Mn&&!b[Mn]) Mn++;
	}
	return 1;
}
void dfs(int x,int rest)
{
	if(x==k-1)
		return a[x]=rest,ans+=check(),void();
	for(int i=0;i<=rest;i++) a[x]=i,dfs(x+1,rest-i);
}
int main()
{
	freopen("count.in","r",stdin);
	freopen("count.out","w",stdout);
	T2=read(),k=read();
	for(int i=1;i<=T2;i++) numr[i]=read();
	reverse(numr+1,numr+T2+1);
	numl[1]=1;
	for(;T2&&numl[T2]==numr[T2];T2--);
	if(!T2) return puts("1"),0;
	dfs(0,T2);
	cout<<ans<<endl;
	fclose(stdin);fclose(stdout);
	return 0;
}
